package com.cdy.demo.algorithm;

public class Leetcode416 {

    public static void main(String[] args) {

    }

    /**
     * 416 拆分数组
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {

        int len = nums.length;
        int  sum= 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }
        int half = sum / 2;

        boolean[][] dp = new boolean[len + 1][half + 1];


        for (int i = 0; i < len+1; i++) {
            for (int j = 0; j < half + 1; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j]=true;
                } else if (i == 0) {
                    dp[i][j]=false;
                } else if (j == 0) {
                    dp[i][j]=true;
                } else {
                    if (j>=nums[i-1])
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[len][half];
    }
}
